Zarankiewicz's problem for semi-algebraic hypergraphs

摘要

Zarankiewicz's problem asks for the largest possible number of edges in agraph that does not contain $K_{u,u}$. Recently, Fox, Pach, Sheffer, Sulk andZahl considered this problem for semi-algebraic graphs, whose vertices arepoints in $\mathbb{R}^d$ and edges are defined by some semi-algebraicrelations. In this paper, we extend this idea to semi-algebraic hypergraphs.For each $k\geq 2$, we found a bound for the maximum number of hyperedges in a$k$-uniform $k$-partite semi-algebraic hypergraph without $K_{u_1,\dots,u_k}$.When $k=2$, this bound matches the one of Fox et.al. and when $k=3$, it is$$O\left((mnp)^{\frac{2d}{2d+1}+\epsilon}+m(np)^{\frac{d}{d+1}+\epsilon}+n(mp)^{\frac{d}{d+1}+\epsilon}+p(mn)^{\frac{d}{d+1}+\epsilon}+mn+np+pm\right),$$where $m,n,p$ are the sizes of 3 partites of the hypergraph and $\epsilon$ isan arbitrarily small positive constant. We then present applications of thisresult to some variant of the unit area problem, to the unit minor problem andto intersection hypergraphs.